package com.bang.study.day02;

import com.bang.study.util.ArrayUtil;

/**
 * @Auther: Bang
 * @Date: 2019/9/23 0023 16:16
 * @Description: 归并排序(迭代器实现) 时间复杂度O(nlogn)
 */
public class MergeSortIteration {

    /**
     *
     * @param arr
     */
    public static void sort(Integer[] arr) {
        int length = arr.length;
        // step <<= 1 <==> step = step << 1 即step扩大一倍
        for (int step = 1; step <length ; step <<= 1) {
            int offset = step + step;
            for (int index = 0; index+step < length; index += offset){
                merge(arr, index, index + step - 1, Math.min(index + offset - 1, length - 1));
            }
        }
    }

    /**
     * 将arr[l...mid]和arr[mid+1...r]两部分进行归并
     *
     * @param arr    目标数组
     * @param left   左边界
     * @param middle 中间
     * @param right  右边界
     */
    static void merge(Integer[] arr, int left, int middle, int right) {
        // 临时数组 存储归并的信息
        Integer[] temp = new Integer[right - left + 1];
        // 缓存左数组第一个元素的索引 用于copy
        int tmp = left;
        // 左边数组第一个元素的索引位置
        int i = left;
        // 右边数组第一个元素的索引位置
        int j = middle + 1;
        // 记录临时数组的索引
        int k = 0;
        while (i <= middle && j <= right) {
            // // 从两个数组中取出最小的放入临时数组
            if (arr[i] <= arr[j]) {
                temp[k] = arr[i];
                i++;
            } else {
//                arr[i] > arr[j]
                temp[k] = arr[j];
                j++;
            }
            k++;
        }
        // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        while (i <= middle) {
            temp[k++] = arr[i++];
        }

        // 将临时数组中的内容拷贝回原数组中
        // （原left-right范围的内容被复制回原数组）
        for (int l = 0; l < temp.length; l++) {
            arr[tmp++] = temp[l];
        }

    }


    public static void main(String[] args) {
        Integer[] array = ArrayUtil.generateRandomArray(4, 0, 20);
        ArrayUtil.printArray(array,4);
        sort(array);
        ArrayUtil.printArray(array, 4);
    }
}
